Decisiones imperfectas en juegos de dos adversarios
Decisión imperfecta ? Estrategia Mixta
El algoritmo minimax asume una expansión hasta el final (en realidad es imposible).
Se usa una función de evaluación (f), que sea una estimación de u.
Función de evaluación:
El papel de f es el de u en nodos terminales
Ejemplos:
Si hay 50% posibilidades de ganar, 25% de perder y 25% de empate,
f=1*0.50+(-1)*0.25+0*0.25=0.25
En el ajedrez: peón=1, alfil=3, …. Suponiendo que MAX=fichas-blancas:
f=(num-peones-negros)*1 + (num-alfiles-negros)*3 …. -(num-peones-blancos)*1 – (num-alfiles-blancos)*3 ….
Decisiones imperfectas en juegos de dos adversarios
Dada una función de evaluación f, se puede aplicar una búsqueda minimax con límite de profundidad:
Se elige un límite de profundidad
Observación: el límite puede tener una posición desventajosa en un nivel más abajo.
Se pueden elegir sucesivos límites de profundidad.
El límite de profundidad se debería aplicar sólo a posiciones “inactivas”.
En ajedrez, serían por ejemplo posiciones en las que es poco probable que existan capturas
Problema del horizonte
Surge cuando el programa se enfrenta a una acción del oponente, inevitable y que causa serios perjuicios.
Ejemplo: en la figura anexa, peón blanco amenaza convertirse en dama. Torre negra amenaza con jaque. La ventaja actual es negra y la inmediata futura es blanca (evaluación calidad piezas).
Decisiones imperfectas en juegos de dos adversarios
Exploración y evaluación:
El procedimiento de exploración visto separa por completo el proceso de generación del árbol de exploración y la evaluación de posiciones.
Se puede reducir el esfuerzo requerido si se hace evaluación de los nodos finales y se llevan hacia atrás esas evaluaciones con la generación el árbol
Fcd-max: número de filas, columnas o diagonales libres para MAX
Fcd-min: número de filas, columnas o diagonales libres para MIN
Ejemplo: Tres en raya
Definimos la función de utilidad:
Decisiones imperfectas en juegos de dos adversarios
Ejemplo: Tres en raya
ver Nilsson
Poda
Consiste en tratar de localizar la decisión óptima minimax sin tener que explorar todos los nodos del árbol.
Aplicable a árboles de cualquier profundidad
Puede podar subárboles enteros
Principio general
El algoritmo efectúa una búsqueda
en profundidad. Si durante la misma se produce que m es mejor que n para un jugador, entonces nunca se llegará a n en el juego
Fundamentos del algoritmo de poda:
Si n es ascendiente de m, si se verifica alguna de estas condiciones:
Si n nodo MAX, m nodo MIN: el valor alpha se alcanza en nodo hijo de n
n nodo MIN, m nodo MAX: el valor alpha se alcanza en nodo hijo de n
En ambos casos no hace falta seguir examinando por debajo de m (se producen podas). El nodo m no afecta al resultado final y es prescindible.
Definimos
Un valor es una cota inferior para el valor obtenido por propagación.
Un valor es una cota superior para el valor obtenido por propagación.
Poda
Algoritmo
(Russell & Norvig)
Poda
Es similar al minimax salvo sendas líneas en
las rutinas MIN-VALUE y MAX-VALUE que mantienen
los valores de alpha y beta
Estimación en el ajedrez
Un agente puede examinar unas 1000 posiciones/segundo.
Si tenemos 150 segundos para pensar un movimiento, entonces, como b es aproximadamente 35, podemos descender 3 ó 4 niveles en el árbol.
La poda va a permitir bajar hasta más niveles.
Ejemplos, I
3
12
8
2
4
6
14
5
2
(Gp:) =3
(Gp:) < =2
(Gp:) =2
(Gp:) =3
Ejemplo sencillo de poda
Ejemplos, II
“2”
“5”
“1”
2
“7”
“3”
6
4
“0”
3
“5”
“1”
9
6
2
8
[? ?]
[-??]
[-??]
[-??]
[-??]
(Gp:) [-?”2”]
(Gp:) [“2” ?]
(Gp:) [2 ?]
(Gp:) [“2” 1]
(Gp:) [-?2]
(Gp:) [-?2]
(Gp:) [-?2]
(Gp:) [-?”2”]
(Gp:) No mejoran ? = 2
(Gp:) [2 ”2”]
? > ? !
? = ? !
? = ? !
(Gp:) [-?”2”]
(Gp:) No mejora valor de ? (lo devuelve hacia arriba)
(Gp:) [2 ?]
(Gp:) [2 ?]
(Gp:) [2 ?]
(Gp:) [2 ?]
(Gp:) [“2” 0]
? > ? !
(Gp:) [“2” ?]
(Gp:) [“2” 2]
(Gp:) [2 ?]
(Gp:) [2 5]
(Gp:) [“2” 1]
Efectividad de la poda
La poda depende del orden en que se examinan los nodos
En el ejemplo de la página siguiente, no se producen podas por debajo del nodo n porque la rama se expande la última.
Si se pudiera elegir el nodo más conveniente (el nodo de f mínima en el caso de MIN):
Knuth y Moore [1], demostraron que la complejidad temporal es:
Por tanto, el factor de ramificación efectivo sería en lugar de b.
En el ajedrez tendríamos
Podríamos bajar hasta el nivel 8.
Es una situación ideal (supondría expandir los nodos para calcular el de menor f).
[1] Donald E. Knuth; Ronald W. Moore; An analysis of alpha-beta pruning. Artificial Intelligence 6(4); 293-326 (1975)
Efectividad de la poda
Knuth y Moore demostraron también que si examinan los sucesores de forma aleatoria para valores moderados de b, la complejidad temporal es aproximadamente:
O(b 3d/4)
3
12
8
2
4
6
14
5
2
n
[-??]
[-??]
[-?, 3]
[3, ?]
[3, ?]
[3, 2]
[3, ?]
[3, 14]
[3, 5]
[3, 2]
 Página anterior | Volver al principio del trabajo | Página siguiente  |